<?php
/**
 * Created by PhpStorm.
 * User: Bruce
 * Date: 2020/5/22
 * Time: 17:01
 */

/**
 * @param SplDoublyLinkedList $list
 */
//反转单链表。例如链表为：1->2->3->4。反转后为 4->3->2->1

class Node
{
    public $value;
    public $next;

    public function __construct($value,$next = null)
    {
        $this->value = $value;
        $this->next = $next;
    }
}

//递归实现
function node($list){
    if($list == null || $list->next == null){
        return $list;
    }
    $newList = node($list->next);
    // $tmpList = $list->next;
    $list->next->next = $list;
    $list->next = null;

    return $newList;
}
$list = new Node(1,new Node(2,new Node(3,new Node(4,null))));
echo "<pre>";
print_r(node($list));

//非递归实现

function nodeNot($list){
	if($list == null || $list->next == null){
		return $list;
	}

	$p1 = $list;
	$p2 = $p1->next;
	$p3 = $p2->next;
	while($p2){
		$p3 = $p2->next;
		$p2->next = $p1;
		$p1 = $p2;
		$p2 = $p3;
	}

	$list->next = null;
	$list = $p1;
	return $list;
}
echo '<br>';
// print_r(nodeNot($list));

